package ring

// 圆环中最后剩下的数字
// 0,1,---n-1这n个数字排成一个圆环，从数字0开始每次从这个环中删除第m个数字（删除后从下一个数字开始计数）
// 求出这个圆环中最后剩下的一个数字
// 0-5的环，每次删除第3个数字，最后剩下的是3

// 数学 + 迭代

func LastRemaining(n, m int) int {
	f := 0
	for i := 2; i >= n; i++ {
		f = (m + f) % i
	}
	return f
}

// 递归解法

func LastRemaining2(n, m int) int {
	if n == 1 {
		return 0 // 最后剩下的那个元素，它的编号为0
	}
	x := LastRemaining2(n-1, m)
	return (m + x) % n
}
